/*
 **********************************************************
 *
 * Programme : listesChainees.c
 * ecrit par : Clément HOSOTTE, Jean-Baptiste FUSS
 *
 * resume : fichier source contenant des fonctions utiles
 * à la manipulation des listes chaînées simples.
 *
 *
 * date : 29/09/2014
 *
 *
 ***********************************************************
 */

#include <stdlib.h>
#include "listesChainees.h"

/*
 * Fonction : ajouterEnTete
 *
 * Parametres :
 * TypVoisins* liste: une liste chaînée
 * int valeur: la valeur (entier) du nouvel élément à insérer
 * int ponderation: la valeur pondérée à ajouter
 *
 * Retour : un pointeur sur le premier élément de la liste
 *
 * Description : Fonction permettant d'ajouter un nouvel élément
 * dans une liste chaînée simple.
 *
 */

TypVoisins* ajouterEnTete(TypVoisins* liste, int valeur, int ponderation){
    /* On crée un nouvel élément */
    TypVoisins* nouvelElement = malloc(sizeof(TypVoisins));
    /* On assigne la valeur au nouvel élément */
    nouvelElement->voisin = valeur;  
    /* On assigne la pondération au nouvel élément*/
    nouvelElement->ponderation = ponderation;   
    /* On assigne l'adresse de l'élément suivant au nouvel élément */
    nouvelElement->voisinSuivant = liste;
    /* On retourne la nouvelle liste, i.e. le pointeur sur le premier élément */
    return nouvelElement;
}

/*
 * Fonction : effacerListe
 *
 * Parametres :
 * TypVoisins* liste: une liste chaînée
 *
 * Retour : la valeur NULL
 *
 * Description : Fonction qui iterer sur une liste chaînée
 * et supprimer ses éléments un à un.
 *
 */
TypVoisins* effacerListe(TypVoisins* liste){
    TypVoisins* tmp = liste;
    TypVoisins* tmpnxt;
    
    /* Tant que l'on n'est pas au bout de la liste */
    while (tmp != NULL) {
        /* On stocke l'élément suivant pour pouvoir ensuite avancer */
        tmpnxt = tmp->voisinSuivant;
        /* On efface l'élément courant */
        free(tmp);
        /* On avance d'une case */
        tmp = tmpnxt;
    }
    /* La liste est vide : on retourne NULL */
    return NULL;
}

/*
 * Fonction : estDansListe
 *
 * Parametres :
 * TypVoisins* liste: une liste chaînée
 * int valeur: un entier identifiant un voisin dans la liste
 *
 * Retour : la valeur 1 si l'élément voisin est présent dans la liste, 0 sinon
 *
 * Description : Fonction qui permet de savoir si un élément 
 * est présent dans une liste
 *
 */
int estDansListe(TypVoisins* liste, int valeur){
	TypVoisins* tmp = liste;
	
	while (tmp != NULL) {
		if (tmp->voisin == valeur) {
			return 1;
		}
		tmp = tmp->voisinSuivant;
	} 
	return 0;
}

/*
 * Fonction : supprimerElement
 *
 * Parametres :
 * TypVoisins*e liste: une liste chaînée
 * int valeur: la valeur de l'élément à supprimer de la liste
 *
 * Retour : NULL soit si l'élément à supprimer n'a pas été trouvé, 
 * soit s'il n'était pas en tête de liste. 
 * Ou dans le cas contraire, l'élément suivant du premier élément 
 * supprimé afin de refaire pointer la liste 
 * vers cet élément dans la fonction appelante.
 *
 * Description : Fonction qui iterer sur une liste chaînée
 * et supprimer l'élément voulu s'il est trouvé
 *
 */
TypVoisins* supprimerElement(TypVoisins* liste, int valeur){
	/* On regarde si l'élément est dans la liste*/
	if (estDansListe(liste,valeur) == 1) {
		TypVoisins *courant = liste;
		TypVoisins *precedent = NULL;
		/* On parcourt la liste pour trouver l'élément à supprimer
		 (et son prédécesseur s'il y en a un) */
		while (courant != NULL && courant->voisin != valeur) {
			precedent = courant;
			courant = courant->voisinSuivant;
		}
		if (precedent != NULL) {
			precedent->voisinSuivant = courant->voisinSuivant;
			free(courant);
			return NULL;
		}
		/* Cas où l'élément est en tête de liste"*/ 
		else {	
			liste = courant->voisinSuivant;
			free(courant);
			/* 
			* On veut retourner le pointeur vers l'élément suivant 
			* pour que la fonction appelante puisse
			* réindexer la liste
			*/
			return liste;
		}
	}
	return NULL;
}

/*
 * Fonction : afficherListe
 *
 * Parametres :
 * TypVoisins* liste: une liste chaînée
 *
 * Retour : void
 *
 * Description : Fonction qui affiche chaque élément 
 * d'une liste simplement chaînée
 * (Rq: le sommet imaginaire -1 n'est jamais affiché)
 *
 */
void afficherListe(TypVoisins* liste)
{
    TypVoisins *tmp = liste;
    /* Tant que l'on n'est pas au bout de la liste */
    while (tmp != NULL) {
        /* Contrôle qu'il y a un voisin suivant*/
        if (tmp->voisin != -1){
            /* On affiche */
            printf("(%d/%d), ", tmp->voisin, tmp->ponderation);
        }
        /* On avance d'une case */
        tmp = tmp->voisinSuivant;
    }
}

